Many combinatorial optimization problems such as the bin packing and multipleknapsack problems involve assigning a set of discrete objects to multiplecontainers. These problems can be used to model task and resource allocationproblems in multi-agent systems and distributed systms, and can also be foundas subproblems of scheduling problems. We propose bin completion, abranch-and-bound strategy for one-dimensional, multicontainer packing problems.Bin completion combines a bin-oriented search space with a powerful dominancecriterion that enables us to prune much of the space. The performance of thebasic bin completion framework can be enhanced by using a number of extensions,including nogood-based pruning techniques that allow further exploitation ofthe dominance criterion. Bin completion is applied to four problems: multipleknapsack, bin covering, min-cost covering, and bin packing. We show that ourbin completion algorithms yield new, state-of-the-art results for the multipleknapsack, bin covering, and min-cost covering problems, outperforming previousalgorithms by several orders of magnitude with respect to runtime on someclasses of hard, random problem instances. For the bin packing problem, wedemonstrate significant improvements compared to most previous results, butshow that bin completion is not competitive with current state-of-the-artcutting-stock based approaches.
展开▼
